import java.util.Arrays;

/**
 * 给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
 * <p>
 * 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
 * <p>
 * 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * 输入：k = 2, prices = [2,4,1]
 * 输出：2
 * 解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
 * 示例 2：
 * <p>
 * 输入：k = 2, prices = [3,2,6,5,0,3]
 * 输出：7
 * 解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4 。
 * 随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。
 *  
 * <p>
 * 提示：
 * <p>
 * 0 <= k <= 100
 * 0 <= prices.length <= 1000
 * 0 <= prices[i] <= 1000
 */
class Solution {

    public static void main(String[] args) {
        System.out.println(maxProfit(2, new int[]{4, 1, 2}));
        System.out.println(maxProfit(2, new int[]{2, 4, 1}));
        System.out.println(maxProfit(2, new int[]{3, 2, 6, 5, 0, 3}));
        System.out.println(maxProfit(1, new int[]{6, 1, 6, 4, 3, 0, 2}));
    }

    private static int[] array;
    private static int[][] dp;
    private static int[][][] remark;

    /**
     * dp表存储i-j的最大利润
     * 状态机递归下去
     * 备忘录表remark存的是，什么状态下，k次的情况下，剩余的最大利润
     *
     * @param prices
     * @return
     */
    public static int maxProfit(int k, int[] prices) {
        if (prices.length <= 1 || k < 1) {
            return 0;
        }
        k = Math.min(k, prices.length / 2 + 1);
        array = prices;
        dp = new int[prices.length][prices.length];
        remark = new int[2][k + 1][prices.length];
        for (int j = 0; j <= k; j++) {
            Arrays.fill(remark[0][j], -1);
            Arrays.fill(remark[1][j], -1);
        }
        for (int end = 1; end < prices.length; end++) {
            for (int start = end, tmp = 0, max = 0; start >= 0; start--) {
                if (prices[start] > max) {
                    max = prices[start];
                } else {
                    tmp = Math.max(tmp, max - prices[start]);
                }
                dp[start][end] = tmp;
            }
        }
        return buy(k, 0);
    }

    /**
     * 处于需要买的状态
     *
     * @param k
     * @param x
     * @return
     */
    private static int buy(int k, int x) {
        if (x >= array.length - 1 || k == 0) {
            return 0;
        }
        if (remark[0][k][x] != -1) {
            return remark[0][k][x];
        }
        // 在x这个节点，可以买入，也可以跳过，递归下去
        int res = Math.max(sell(k - 1, x, x + 1), buy(k, x + 1));
        remark[0][k][x] = res;
        return res;
    }

    /**
     * 处于需要卖的状态
     *
     * @param k
     * @param x
     * @param y
     * @return
     */
    private static int sell(int k, int x, int y) {
        if (y >= array.length || k == -1) {
            return 0;
        }
        if (remark[1][k][x] != -1) {
            return remark[1][k][x];
        }
        // 在y这个节点，可以卖出，也可以跳过，递归下去
        int res = Math.max(dp[x][y] + buy(k, y + 1), sell(k, x, y + 1));
        remark[1][k][x] = res;
        return res;
    }


}